// #include <iostream>  
// #include <vector>  
// #include <algorithm>  

// // 使用别名Rank代替int  
// typedef int Rank;

// // 二分查找函数版本A  
// // 在有序向量v的[lo, hi)范围内查找e，返回其位置。若未找到，则返回-1  
// Rank binSearchA(const std::vector<int>& v, int e, Rank lo, Rank hi) {
//     while (lo < hi) {
//         Rank mi = lo + (hi - lo) / 2; // 相当于(lo + hi) / 2，但可防止整数溢出  
//         if (e < v[mi]) {
//             hi = mi;
//         }
//         else if (v[mi] < e) {
//             lo = mi + 1;
//         }
//         else {
//             return mi;
//         }
//     }
//     return -1; // 未找到  
// }
// Rank binSearchC(const std::vector<int>& v, int e, Rank lo, Rank hi) {
//     while (lo < hi) {
//         Rank mi = lo + (hi - lo) / 2; // 相当于(lo + hi) / 2，但可防止整数溢出  

//         (e < v[mi]) ? hi = mi : lo = mi + 1;
//     }
//     return --lo;
//     // 未找到  
// }
// int main() {
//     std::vector<int> UnSorted = { 2,5,4,7,4,9,8,9,12 };
//     std::vector<int> Sorted = UnSorted; // 复制原始向量以进行排序  

//     // 对向量进行升序排序  
//     std::sort(Sorted.begin(), Sorted.end());


//     std::cout << "用binSearchA在 [1, 8)搜索4:: " << binSearchA(Sorted, 4, 1, 8) << std::endl;
//     std::cout << "用binSearchC在 [1, 8)搜索4:: " << binSearchC(Sorted, 4, 1, 8) << std::endl;

//     std::cout << "用binSearchA在 [1, 8)搜索9:: " << binSearchA(Sorted, 9, 1, 8) << std::endl;
//     std::cout << "用binSearchC在 [1, 8)搜索9:: " << binSearchC(Sorted, 9, 1, 8) << std::endl;

//     std::cout << "用binSearchA在 [1, 8)搜索2:: " << binSearchA(Sorted, 2, 1, 8) << std::endl;
//     std::cout << "用binSearchC在 [1, 8)搜索2:: " << binSearchC(Sorted, 2, 1, 8) << std::endl;

//     std::cout << "用binSearchA在 [1, 8)搜索12:: " << binSearchA(Sorted, 12, 1, 8) << std::endl;
//     std::cout << "用binSearchC在 [1, 8)搜索12:: " << binSearchC(Sorted, 12, 1, 8) << std::endl;
//     return 0;
// }



// #include <iostream>
// #include <vector>
// #include <algorithm> // 包含排序函数
// using namespace std;

// int binSearchA(const vector<int>& arr, int low, int high, int target) {
//     while (low < high) { // 注意这里是 low < high，表示左闭右开的区间
//         int mid = low + (high - low) / 2;
//         if (arr[mid] == target) {
//             return mid;
//         }
//         else if (arr[mid] < target) {
//             low = mid + 1;
//         }
//         else {
//             high = mid;
//         }
//     }
//     return -1;
// }

// int main() {
//     // SortedVector31
//     vector<int> sorted_vector_31 = { 2, 5, 4, 9, 8, 12, 7 };

//     // 对向量进行排序
//     sort(sorted_vector_31.begin(), sorted_vector_31.end());

//     // (1) 在区间[1,5)，搜索7，并输出返回值
//     int result_1 = binSearchA(sorted_vector_31, 1, 5, 7);
//     cout << "(1) 搜索7的结果: " << result_1 << endl;

//     // (2) 在区间[1,5)，搜索2，并输出返回值
//     int result_2 = binSearchA(sorted_vector_31, 1, 5, 2);
//     cout << "(2) 搜索2的结果: " << result_2 << endl;

//     // (3) 在区间[1,5)，搜索12，并输出返回值
//     int result_3 = binSearchA(sorted_vector_31, 1, 5, 12);
//     cout << "(3) 搜索12的结果: " << result_3 << endl;

//     return 0;
// }



// #include <iostream>
// #include <vector>

// typedef int Rank; // 别名Rank代替int

// // 二分查找函数版本B
// Rank binSearchB(const std::vector<int>& vec, int target, Rank low, Rank high) {
//     while (low < high) {
//         Rank mid = low + (high - low) / 2;
//         if (vec[mid] < target) {
//             low = mid + 1;
//         }
//         else if (vec[mid] > target) {
//             high = mid;
//         }
//         else {
//             return mid; // 找到目标值时直接返回索引
//         }
//     }
//     return -1; // 未找到目标值时返回-1
// }

// int main() {
//     std::vector<int> SortedVector31 = { 2, 4, 5, 7, 8, 9, 12 }; // 排序后的向量

//     // (1) 在区间[1,5)，搜索7
//     Rank result1 = binSearchB(SortedVector31, 7, 1, 5);
//     std::cout << "搜索7的结果：" << result1 << std::endl;

//     // (2) 在区间[1,5)，搜索2
//     Rank result2 = binSearchB(SortedVector31, 2, 1, 5);
//     std::cout << "搜索2的结果：" << result2 << std::endl;

//     // (3) 在区间[1,5)，搜索12
//     Rank result3 = binSearchB(SortedVector31, 12, 1, 5);
//     std::cout << "搜索12的结果：" << result3 << std::endl;

//     return 0;
// }


#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef int Rank;

//template<typename T>  static Rank bin_c(T *a, T const &e, Rank lo, Rank hi)

Rank bin_c(const std::vector<int>& a, int e, Rank lo, Rank hi) {
	while (lo < hi) {
		Rank mi = (lo + hi) >> 1;
		(e < a[mi]) ? hi = mi : lo = mi + 1;
	}
	return --lo;
}

int main() {
	std::vector<int> v32 = { 2, 5, 4, 9, 8, 12, 7 };
	std::vector<int> s = v32;
	std::sort(s.begin(), s.end());
	cout << "在区间[1,5)中搜索目标值为7，返回结果：" << bin_c(s, 7, 1, 5) << endl;
	cout << "在区间[1,5)中搜索目标值为2，返回结果：" << bin_c(s, 2, 1, 5) << endl;
	cout << "在区间[1,5)中搜索目标值为12，返回结果：" << bin_c(s, 12, 1, 5) << endl;
	return 0;
}